package com.example.system.class10;

/**
 * @Date 2022/7/30
 * @Author Jonathan
 */
public class Code01_LinkedListMid {


    public static void main(String[] args) {
        int[] arr = new int[]{1, 2};
        Node head = createLink(arr);
        System.out.println("奇数长度返回中点，偶数长度返回上中点:" + getMid1(head));
        System.out.println("奇数长度返回中点，偶数长度返回下中点:" + getMid2(head));
        arr = new int[]{1, 4, 3};
        head = createLink(arr);
        System.out.println("奇数长度返回中点，偶数长度返回上中点:" + getMid1(head));
        System.out.println("奇数长度返回中点，偶数长度返回下中点:" + getMid2(head));
        // todo  中点的前一个节点怎么找？
    }


    static class Node {
        Node next;
        int value;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node[" +
                    "value=" + value +
                    ']';
        }
    }

    public static Node createLink(int[] arr) {
        if (arr == null || arr.length <= 0) {
            return null;
        }
        Node root = new Node(arr[0]);
        Node cur = root;
        for (int i = 1; i < arr.length; i++) {
            final Node node = new Node(arr[i]);
            cur.next = node;
            cur = node;
        }
        return root;
    }


    /**
     * 1、输入链表头节点，奇数长度返回中点，偶数长度返回上中点
     */
    public static Node getMid1(Node head) {
        Node slow = head;
        Node fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 2、入链表头节点，奇数长度返回中点，偶数长度返回下中点
     */

    public static Node getMid2(Node head) {
        // 0-1个节点
        if (head == null || head.next == null) {
            return head;
        }
        // 2个节点
        if (head.next.next == null) {
            return head.next;
        }
        // 至少三个节点
        Node slow = head.next;
        Node fast = head.next.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 3、输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
     */
    public static Node getMid3(Node head) {

        return head;
    }
}
